public class 预测赢家 {
    // 递归
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        int sum = 0;
        // 总和计算
        for (int num : nums) {
            sum += num;
        }
        // 先手者最多能获得多少
        int first = dfs(nums,0,n - 1);
        int second = sum - first;
        return first >= second;
    }
    public int dfs (int[] nums,int l, int r) {
        // 如果只剩一个, 自己拿了
        if (r == l) {
            return nums[l];
        }
        // 剩两个选择大的
        if(l + 1 == r) {
            return Math.max(nums[l],nums[r]);
        }
        // 拿左边的, 因为对方也很聪明, 所以选择两者之中少的
        int p1 = nums[l] + Math.min(dfs(nums,l + 2,r),dfs(nums,l + 1,r - 1));
        // 拿右边的, 选择两种情况之中少的
        int p2 = nums[r] + Math.min(dfs(nums,l,r - 2),dfs(nums,l + 1,r - 1));
        // 取最大值
        return Math.max(p1,p2);
    }

}
